home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_2 / hash.str < prev    next >
Text File  |  1995-03-23  |  6KB  |  394 lines
  1. Article 2129 of comp.sys.handhelds:
  2. Path: en.ecn.purdue.edu!noose.ecn.purdue.edu!samsung!usc!apple!snorkelwacker!ai-lab!rice-chex!bson
  3. From: bson@rice-chex.ai.mit.edu (Jan Brittenson)
  4. Newsgroups: comp.sys.handhelds
  5. Subject: String hashing on the HP-48
  6. Message-ID: <11654@life.ai.mit.edu>
  7. Date: 31 Oct 90 09:00:58 GMT
  8. Sender: news@ai.mit.edu
  9. Organization: nil
  10. Lines: 380
  11.  
  12.  
  13.    Here is a simple string hashing program. It takes a string as an
  14. argument; it returns in level 2 the string with its first character
  15. incremented, and in level 1 a short integer hash value. It doesn't
  16. check for an empty stack, or that the argument actually is a string.
  17. Be careful - embed it suitably. It's an additive version of the XOR
  18. (for lack of a Saturn XOR instruction) algorithm described in the June
  19. 1990 issue of CACM (Peter Pearson: _Fast Hashing Of Variable-Length
  20. Text Strings_).
  21.  
  22.    The incrementation of the first character aids in computing larger
  23. hash values.
  24.  
  25.  
  26. Load the hex data and convert it with ASC->.
  27.  
  28. %%HP: T(3)A(R)F(.);
  29. "CCD2057200D6061438FB97608FCC021D88A82414BB64149808240700007CA130
  30. D014F171A6A136134A64C213614A136CD8ADED81AF008F2D7608DA0D8101F797
  31. 49683FD91D55A52630F2659859C5564876A7DFFB3736898290FC6270E469CDE6
  32. E70679575F735E6EFAB4AABCF5CBDA78630442B2ED15C0D4EF67DE8774D738C8
  33. E8B0B82F8E358D40D25A524ABDF6CE7FDD7CCCBA4521B13C71E1C7ADF93D9408
  34. 5092F46124D0B79DC40D29BB519554105C6B33DC9319DBCA2EEE66A90F169B6F
  35. C2FF7A1C9AA2CF1F7EC63AB3AE1B9F6CA044C11EC9B903D69EE36460750BEAFD
  36. E0224641200C05F3A1112C1AEB72278FA4533EE228F10A8458835BF0C3D8BFD5
  37. 43E59907EC5D2A7B8C806AAB8BF86DFE9100BE394B77D32B9614E902174C0E4D
  38. A812478588134F4E238A3B818631AFD1A3AC0932252D9C7D1834B5A6B6F906"
  39.  
  40. Store it in 'HASH'.
  41.  
  42. A simple example:
  43.  
  44. \<< "" + HASH
  45.    # 60F9Bh SYSEVAL        @ Drop level 2
  46.    # 18DBFh SYSEVAL        @ Short to real
  47. \>>
  48.  
  49.  
  50. Null strings always yield 0.
  51.  
  52. And, finally, the source code, ASAP style.
  53.  
  54.  
  55. O  /
  56.  \/
  57.  /\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  58. O  \
  59.  
  60. ;;+
  61. ;;  HASH -- Hash string
  62. ;; 
  63. ;;  Synopsis:
  64. ;;    Hash string in level 1. Return string with first character
  65. ;;    incremented in level 2. Return hash value in level 1.
  66. ;;
  67. ;; bson@ai.mit.edu, Oct 31, 1990
  68. ;;
  69. ;;-
  70.  
  71. save_regs=#679b
  72. restore_regs=#67d2
  73. strlen_a=#120cc
  74. shortpush_r0_rplret=#18d0a
  75.  
  76. ; Std.preamble
  77.  
  78.     data.b    'H'
  79.     data.b    'P'
  80.     data.b    'H'
  81.     data.b    'P'
  82.     data.b    '4'
  83.     data.b    '8'
  84.     data.b    '-'
  85.     data.b    'D'
  86.     data.a    #2dcc
  87. begin:    data.a    end-begin
  88.  
  89. ; Enter here
  90.  
  91. hash:
  92.     move.a    a,c
  93.     push.a    c
  94.     move.a    @d1,a
  95.     call.a    save_regs
  96.     call.a    strlen_a
  97.     move.a    a,b            ; B = length of string in bytes
  98.     brz.a    a,hash_exit
  99.  
  100.     move.b    @d1,a            ; Increment the first char
  101.     inc.b    a
  102.     move.b    a,@d1
  103.  
  104.     move.p5    hash_table,a        ; Set D0 to table start
  105.     pop.a    c
  106.     add.a    c,a
  107.     move.a    a,d0
  108.  
  109.     clr.a    a            ; Start with 0 hash value
  110.  
  111. hash_loop:
  112.     move.b    @d1,c            ; Next char
  113.     add.a    2,d1
  114.     add.b    c,a            ; Add to prev hash value
  115.  
  116.     swap.a    c,d0
  117.     move.a    c,d0
  118.     add.b    a,a
  119.     add.a    a,c
  120.     swap.a    c,d0            ; D0 = 2*char+table
  121.     move.b    @d0,a            ; Get new hash value from table
  122.     swap.a    c,d0
  123.     
  124.     dec.a    b            ; Loop chars
  125.     brnz.a    b,hash_loop
  126. hash_exit:
  127.     move.a    a,r0
  128.     call.a    restore_regs
  129.     jump.a    shortpush_r0_rplret
  130.  
  131. ; Random permutations of 00-ff
  132.  
  133. dummy:
  134. hash_table=dummy-hash
  135.     data.b    #10
  136.     data.b    #7f
  137.     data.b    #79
  138.     data.b    #94
  139.     data.b    #86
  140.     data.b    #f3
  141.     data.b    #9d
  142.     data.b    #d1
  143.     data.b    #55
  144.     data.b    #5a
  145.     data.b    #62
  146.     data.b    #3
  147.     data.b    #2f
  148.     data.b    #56
  149.     data.b    #89
  150.     data.b    #95
  151.     data.b    #5c
  152.     data.b    #65
  153.     data.b    #84
  154.     data.b    #67
  155.     data.b    #7a
  156.     data.b    #fd
  157.     data.b    #bf
  158.     data.b    #73
  159.     data.b    #63
  160.     data.b    #98
  161.     data.b    #28
  162.     data.b    #9
  163.     data.b    #cf
  164.     data.b    #26
  165.     data.b    #7
  166.     data.b    #4e
  167.     data.b    #96
  168.     data.b    #dc
  169.     data.b    #6e
  170.     data.b    #7e
  171.     data.b    #60
  172.     data.b    #97
  173.     data.b    #75
  174.     data.b    #f5
  175.     data.b    #37
  176.     data.b    #e5
  177.     data.b    #e6
  178.     data.b    #af
  179.     data.b    #4b
  180.     data.b    #aa
  181.     data.b    #cb
  182.     data.b    #5f
  183.     data.b    #bc
  184.     data.b    #ad
  185.     data.b    #87
  186.     data.b    #36
  187.     data.b    #40
  188.     data.b    #24
  189.     data.b    #2b
  190.     data.b    #de
  191.     data.b    #51
  192.     data.b    #c
  193.     data.b    #4d
  194.     data.b    #fe
  195.     data.b    #76
  196.     data.b    #ed
  197.     data.b    #78
  198.     data.b    #47
  199.     data.b    #7d
  200.     data.b    #83
  201.     data.b    #8c
  202.     data.b    #8e
  203.     data.b    #b
  204.     data.b    #8b
  205.     data.b    #f2
  206.     data.b    #e8
  207.     data.b    #53
  208.     data.b    #d8
  209.     data.b    #4
  210.     data.b    #2d
  211.     data.b    #a5
  212.     data.b    #25
  213.     data.b    #a4
  214.     data.b    #db
  215.     data.b    #6f
  216.     data.b    #ec
  217.     data.b    #f7
  218.     data.b    #dd
  219.     data.b    #c7
  220.     data.b    #cc
  221.     data.b    #ab
  222.     data.b    #54
  223.     data.b    #12
  224.     data.b    #1b
  225.     data.b    #c3
  226.     data.b    #17
  227.     data.b    #1e
  228.     data.b    #7c
  229.     data.b    #da
  230.     data.b    #9f
  231.     data.b    #d3
  232.     data.b    #49
  233.     data.b    #80
  234.     data.b    #5
  235.     data.b    #29
  236.     data.b    #4f
  237.     data.b    #16
  238.     data.b    #42
  239.     data.b    #d
  240.     data.b    #7b
  241.     data.b    #d9
  242.     data.b    #4c
  243.     data.b    #d0
  244.     data.b    #92
  245.     data.b    #bb
  246.     data.b    #15
  247.     data.b    #59
  248.     data.b    #45
  249.     data.b    #1
  250.     data.b    #c5
  251.     data.b    #b6
  252.     data.b    #33
  253.     data.b    #cd
  254.     data.b    #39
  255.     data.b    #91
  256.     data.b    #bd
  257.     data.b    #ac
  258.     data.b    #e2
  259.     data.b    #ee
  260.     data.b    #66
  261.     data.b    #9a
  262.     data.b    #f0
  263.     data.b    #61
  264.     data.b    #b9
  265.     data.b    #f6
  266.     data.b    #2c
  267.     data.b    #ff
  268.     data.b    #a7
  269.     data.b    #c1
  270.     data.b    #a9
  271.     data.b    #2a
  272.     data.b    #fc
  273.     data.b    #f1
  274.     data.b    #e7
  275.     data.b    #6c
  276.     data.b    #a3
  277.     data.b    #3b
  278.     data.b    #ea
  279.     data.b    #b1
  280.     data.b    #f9
  281.     data.b    #c6
  282.     data.b    #a
  283.     data.b    #44
  284.     data.b    #1c
  285.     data.b    #e1
  286.     data.b    #9c
  287.     data.b    #9b
  288.     data.b    #30
  289.     data.b    #6d
  290.     data.b    #e9
  291.     data.b    #3e
  292.     data.b    #46
  293.     data.b    #6
  294.     data.b    #57
  295.     data.b    #b0
  296.     data.b    #ae
  297.     data.b    #df
  298.     data.b    #e
  299.     data.b    #22
  300.     data.b    #64
  301.     data.b    #14
  302.     data.b    #2
  303.     data.b    #c0
  304.     data.b    #50
  305.     data.b    #3f
  306.     data.b    #1a
  307.     data.b    #11
  308.     data.b    #c2
  309.     data.b    #a1
  310.     data.b    #be
  311.     data.b    #27
  312.     data.b    #72
  313.     data.b    #f8
  314.     data.b    #4a
  315.     data.b    #35
  316.     data.b    #e3
  317.     data.b    #2e
  318.     data.b    #82
  319.     data.b    #1f
  320.     data.b    #a0
  321.     data.b    #48
  322.     data.b    #85
  323.     data.b    #38
  324.     data.b    #b5
  325.     data.b    #f
  326.     data.b    #3c
  327.     data.b    #8d
  328.     data.b    #fb
  329.     data.b    #5d
  330.     data.b    #34
  331.     data.b    #5e
  332.     data.b    #99
  333.     data.b    #70
  334.     data.b    #ce
  335.     data.b    #d5
  336.     data.b    #a2
  337.     data.b    #b7
  338.     data.b    #c8
  339.     data.b    #8
  340.     data.b    #a6
  341.     data.b    #ba
  342.     data.b    #b8
  343.     data.b    #8f
  344.     data.b    #d6
  345.     data.b    #ef
  346.     data.b    #19
  347.     data.b    #0
  348.     data.b    #eb
  349.     data.b    #93
  350.     data.b    #b4
  351.     data.b    #77
  352.     data.b    #3d
  353.     data.b    #b2
  354.     data.b    #69
  355.     data.b    #41
  356.     data.b    #9e
  357.     data.b    #20
  358.     data.b    #71
  359.     data.b    #c4
  360.     data.b    #e0
  361.     data.b    #d4
  362.     data.b    #8a
  363.     data.b    #21
  364.     data.b    #74
  365.     data.b    #58
  366.     data.b    #88
  367.     data.b    #31
  368.     data.b    #f4
  369.     data.b    #e4
  370.     data.b    #32
  371.     data.b    #a8
  372.     data.b    #b3
  373.     data.b    #18
  374.     data.b    #68
  375.     data.b    #13
  376.     data.b    #fa
  377.     data.b    #1d
  378.     data.b    #3a
  379.     data.b    #ca
  380.     data.b    #90
  381.     data.b    #23
  382.     data.b    #52
  383.     data.b    #d2
  384.     data.b    #c9
  385.     data.b    #d7
  386.     data.b    #81
  387.     data.b    #43
  388.     data.b    #5b
  389.     data.b    #6a
  390.     data.b    #6b
  391. end:
  392.  
  393.  
  394.